While more strict regulations for protecting private information and confidential information have come to be enforced, a market for services using such information is now expanding. Furthermore, currently used are concealing technologies allowing the data of private information or confidential information to be used while some protection is applied to the data. Among such concealing technologies, some using encryption or statistical technologies are available, depending on the type of data or service requirements.
A known example of the concealing technology using encryption is a homomorphic encryption technology. Homomorphic encryption is a type of public key encryption using a pair of different keys for encryption and decryption, and is an encryption allowing encrypted data to be operated. For example, the characteristic expressed in Equation (1) or (2) is established for a homomorphic encryption function E related to addition or multiplication of plaintexts m1 and m2.E(m1)+E(m2)=E(m1+m2)  (1)E(m1)*E(m2)=E(m1*m2)  (2)
The encryption for which Equation (1) is established is referred to as being homomorphic for addition, and the encryption for which Equation (2) is established is referred to as being homomorphic for multiplication.
Homomorphic encryption allows addition or multiplication of encrypted texts to output another encrypted text resultant of the operation such as the addition or the multiplication, without requiring decoding of the encrypted texts. This characteristic of the homomorphic encryption is used in fields such as electronic voting, electronic cash, and cloud computing. Representative examples of homomorphic encryption include Rivest Shamir Adleman (RSA) encryption enabled for multiplication, and additive ElGamal encryption enabled for addition.
Homomorphic encryption is recently known for being used for both addition and multiplication. Also known is homomorphic encryption that can be used for both addition and multiplication, and is feasible from the viewpoint of processing performance, as well as from the viewpoint of the encrypted data size.
An exemplary homomorphic encryption will now be explained. Before generating an encryption key, mainly three key generation parameters (n, q, t) are prepared. n herein is an integer that is a power of two, and is referred to as a lattice dimension. q is a prime number, and t is an integer less than the prime number q. The encryption key generation starts from a step of randomly generating an n-dimensional polynomial sk having coefficients that are small as a secret key. The smallness of each coefficient is restricted by a parameter σ. Generated at the subsequent steps are an n-dimensional polynomial a1 each coefficient of which is smaller than q, and another n-dimensional polynomial e having small coefficients.
a0=−(a1*sk+t*e) is then calculated, and the pair (a0, a1) is defined as a public key pk. In calculating the polynomial a0, a polynomial of the degree less than n is always calculated by calculating xn=−1, xn+1=−x, . . . and so on in polynomials of the nth degree or higher. For the coefficients of a polynomial, remainders of dividing the respective coefficients by the prime number q are output. The space for performing such an operation is often scholarly expressed as Rq:=Fq[x]/(xn+1).
At the subsequent step, three n-dimensional polynomials u, f, and g having small coefficients are randomly generated, for a piece of plaintext data m expressed by an nth degree polynomial each coefficient of which is smaller than t, and for the public key pk=(a0, a1). The data Enc(m, pk)=(c0, c1) that is an encryption of the plaintext data m is then defined as follows. (c0, c1) are calculated as c0=a0*u+t*g+m and c1=a1*u+t*f. These calculations are performed as operations in the space Rq.
An encryption addition Enc(m1, pk)+Enc(m2, pk) is performed to two encrypted texts Enc(m1, pk)=(c0, c1) and Enc(m2, pk)=(d0, d1), as (c0+d0, c1+d1), and an encryption multiplication Enc(m1, pk)*Enc(m2, pk) is performed as (c0+d0, c0*d1+c1*d0, c1*d1). It is noted that, when the encryption multiplication is performed in the manner described above, the data size of the encrypted texts is changed from a two-component vector to a three-component vector.
In the decrypting process, the encrypted text c=(c0, c1, c2, . . . ) (it is assumed herein that the number of components of the encrypted text data has increased as a result of encryption operations such as a plurality of encryption multiplications) is decrypted by calculating Dec(c, sk)=[c0+c1*sk+c2*sk2+ . . . ]q mod t, using the secret key sk. A remainder w of dividing an integer z by q is calculated for a value of [z]q. If w<q, [z]q=w is output. If w≧q, [z]q=w-q is output. a mod t herein means a remainder of dividing the integer a by t.
To facilitate understanding, examples using actual numbers will be provided below.secret key sk=Mod(Mod(4,1033)*x3+Mod(4,1033)*x2+Mod(1,1033)*x,x4+1)public key pk=(a0,a1)a0=Mod(Mod(885,1033)*x3+Mod(519,1033)*x2+Mod(621,1033)*x+Mod(327,1033),x4+1)a1=Mod(Mod(661,1033)*x3+Mod(625,1033)*x2+Mod(861,1033)*x+Mod(311,1033),x4+1)Enc(m,pk)=(c0,c1)
It is assumed herein that the plaintext data m=3+2x+2x2+2x3.c0=Mod(Mod(822,1033)*x3+Mod(1016,1033)*x2+Mod(292,1033)*x+Mod(243,1033),x4+1)c1=Mod(Mod(840,1033)*x3+Mod(275,1033)*x2+Mod(628,1033)*x+Mod(911,1033),x4+1)
In these values above, the key generation parameters (n, q, t) are set to (4, 1033, 20), respectively. Mod(a, q) denotes the remainder of dividing the integer a by the prime number q, and Mod(f(x), x4+1) denotes the polynomial that is the remainder of dividing the polynomial f(x) by the polynomial x4+1, where x4=−1, x5=x, . . . , and so on.
There is also a technique for accelerating a secrecy distance computation using homomorphic encryption. The acceleration technique will now be explained. The technique makes use of the characteristic that the encryption scheme described above is enabled for polynomial operation. Specifically, the encryption scheme has a characteristic that, given two encrypted texts Enc(f(x), pk) and Enc(g(x), pk) corresponding to two polynomials f(x) and g(x) of a degree less than n, a polynomial addition can be performed to the encrypted texts as Enc(f(x), pk)+Enc(g(x), pk)=Enc(f(x)+g(x), pk). A polynomial multiplication can also be performed to the encrypted texts as Enc(f(x), pk)*Enc(g(x), pk)=Enc(f(x)*g(x), pk).
Given two vectors A=(a0, a1, . . . ) and B=(b0, b1, . . . ), the acceleration technique calculates the inner product Σai*bi at a high speed, with A and B encrypted. Specifically, an ascending order polynomial Pm1(A)=Σaix^i is generated for the vector A, and a descending order polynomial with a negative sign is generated for the vector B as Pm2(B)=−Σbix^(n−i). These polynomials are then homomorphically encrypted as Enc(Pm1(A), pk), Enc(Pm2(B), pk).
To multiply these two encrypted texts, the polynomial multiplication Pm1(A)*Pm2(B) is performed with these texts encrypted, and the constant term of the multiplication will be the inner product Σai*bi. In other words, the constant term of the decryption result of the encrypted multiplication will exactly be the inner product Σai*bi. With this technique, computation can be performed efficiently, compared with the technique in which each of the components A and B are encrypted and their inner product is computed. Furthermore, by applying this high-speed inner product computation, Hamming distance calculation or L2 norm computation can be performed at a high speed with data encrypted.
An exemplary application that uses the homomorphic encryption and the technique for performing the Hamming distance calculation or the L2 norm computation at a high speed with data encrypted is a biometric authentication system that uses biological information such as a finger print or veins for authentication. In such a biometric authentication system, the confidentiality of the biological information can be improved by performing the Hamming distance calculation to the biological information protected with the homomorphic encryption. A related art example is disclosed in Japanese National Publication of International Patent Application No. 2008-521025.
A biometric authentication system in which the biometric authentication is achieved by performing the Hamming distance calculation to the encrypted biological information, however, has a shortcoming of having difficulty in detecting fraudulent matching data.
Some typical examples of spoofing attacks intended to achieve fraudulent authentication in a biometric authentication system include a retransmission attack by eavesdropping the communication channel, spoofing by inputting biological information using some artifact such as a gummy finger or a printed material, and spoofing by transmitting fraudulent (fake) authentication data.
Specifically, to spoof by transmitting fraudulent matching data, which is one of the example mentioned above, when the Hamming distance calculation is calculated, the attacker will transmit a piece of fraudulent matching data outputting a distance, with respect to biological information (template) registered in advance, that is smaller than a threshold for permitting the authentication to be successful. For example, transmitted is B=(b0, b1, . . . , b2047)=(1, 0, 1, 0, . . . , 1, e) that is the fake authentication data, with respect to a piece of binary data A=(a0, a1, . . . , a2047) registered as a template.
The last component of B is not a piece of binary data, but is a selection of an integer e having the absolute value of 1024-θ, where θ is a threshold for determining whether to allow the authentication to succeed by calculating the Hamming distance with respect to the template. In other words, the authentication succeeds when a distance d (A, B) between the two biological feature vectors (biological information) A and B is smaller than the threshold θ.
In this example, because the distance d(A, B) between the legitimate template A and the fraudulent matching data B is Σ(ai+bi−2ai*bi), the resultant distance may be 50 percent probability, which is smaller than the threshold θ, depending on how e is selected, and the authentication may end up being successful. At this time, because the authentication data is homomorphically encrypted, it is difficult to detect that the data is fraudulent matching data.